НУЛП, ІКНІ, САПР Тема оцінка підпис    Алгоритм рішення задачі комівояжера         № залікової:     Дискретні моделі в САПР  Викладач:       Мета роботи : метою даної лабораторної роботи є вивчення і дослідження алгоритмів рішення задачі комівояжера. Короткі теоретичні відомості : Невідомо, коли проблему комівояжера було досліджено вперше. Однак, відома видана в 1832 році книжка з назвою «Комівояжер — як він має поводитись і що має робити для того, аби доставляти товар та мати успіх в своїх справах — поради старого Кур'єра», в якій описано проблему, але математичний апарат для її розв'язання не застосовується. Натомість, в ній запропоновано приклади маршрутів для деяких регіонів Німеччини та Швейцарії. Раннім варіантом задачі може розглядатись англ. Icosian Game Вільяма Гамільтона 19 століття, яка полягала в тому, щоб знайти маршрути на графі з 20 вузлами. Перші згадки в якості математичної задачі на оптимізацію нелажать Карлу Менґеру (нім. Karl Menger), який сформулював її в математичному колоквіумі в 1930 році наступним чином: ми називаємо проблемою женця (оскільки це питання виникає в кожного листоноші, зокрема, її вирішують багато мандрівників) завдання віднайти найкоротший шлях між скінченною множиною місць, відстань між якими відома. Невдовзі з'явилась відома зараз назва задача мандруючого продавця (англ. Traveling Salesman Problem), яку запропонував Гаслер Вітні (англ. Hassler Whitney) з Принстонського Університету. З метою спрощення задачі та гарантії існування маршруту, зазвичай вважається, що модельний граф задачі є повністю зв'язним, тобто, що між довільною парою вершин існує ребро. Це можна досягти тим, що в тих випадках, коли між окремими містами не існує сполучення, вводити ребра з максимальною вагою (довжиною, вартістю тощо). Через велику довжину таке ребро ніколи не потрапить до оптимального маршруту, якщо він існує. Загальною задачею комівояжера називають задачу пошуку маршруту найменшої довжини. Задачею комівояжера називають задачу пошуку гамільторового контура найменшої довжини. Контур комівояжера, який має найменшу довжину, називають оптимальним гамільтоновим контуром він є оптимальним рішенням задачі комівояжера. Оптимальний маршрут комівояжера не обов`язково є гамільтоновим контуром. Рішенням задачі комівояжера є оптимальний гамільтоновий контур. Реалізація алгоритму (Java) : public void tsp(int adjacencyMatrix[][]) { /* Ініціалізація змінних */ int[] visited = new int[numberOfNodes + 1];//Пройдені вершини int element, distance = 0, i; int min = Integer.MAX_VALUE;  System.out.print(1 + "\t"); while (!stack.isEmpty()) {  /* Доки не пройдено всіх вершин, знаходимо мінімальне ребро, суміжне з вершиною і додаємо його до загальної вартості. */ while (i <= numberOfNodes) { if (adjacencyMatrix[element][i] > 1 && visited[i] == 0) { if (min > adjacencyMatrix[element][i]) { min = adjacencyMatrix[element][i]; distance = i; minFlag = true; } } i++; } /*Якщо ребро задовільняє умови мінімальності ,то додаємо його в шлях і виводимо його(шлях). */ if (minFlag) { cost+=min;  System.out.print(distance + "\t"); }  } } Інструкція по експлуатації: Для роботи програми необхідно запустити файл Lab_4_DM.java . Спочатку необхідно ввести кількість вершин графа, далі матрицю суміжності. Далі програма знаходить мінімальний маршрут та виводить його значення. Граф: Рис.1. Початковий граф. Рис.2. Знайдений маршрут. Результат виконання: ***HELP*** 0. Програма розв'язує задачу к...